package com.cty._01_Base._08_NextNodeInBinaryTrees;

/**
 * @Auther: cty
 * @Date: 2020/6/29 9:41
 * @Description: 面试题8：二叉树的下一个节点
 * 题目：给定一颗二叉树和其中一个节点，如何找出中序遍历序列的下一个节点？
 * 树中的节点除了有两个分别指向左、右子节点的指针，还有一个指向父节点的指针。
 * @version: 1.0
 */
public class NextNodeInBinaryTrees {

    /**
     * 获取二叉树指定节点的中序遍历的下一个节点
     * @param node
     * @return
     */
    public static BinaryTreeNode getNext(BinaryTreeNode node){
        if(node == null)
            return null;  // ① 输入空指针，则返回空指针
        BinaryTreeNode current;

        // 1 若该节点有右子节点
        current = node.rightTree;
        if(current != null){
            while(current.leftChild != null){
                current = current.leftChild;
            }
            return current;  // ② 返回该节点右子节点的最左子节点
        }

        // 2 若该节点无右边子节点，无父节点
        current = node.parent;
        if(current == null)
            return null;  // ③ 返回空指针

        // 3 若该节点无右子节点，有父节点且为父节点的左子节点
        if(current.leftChild == node)
            return current;  // ④ 返回该节点的父节点

        // 4 若该节点无右子节点，有父节点且无父节点的右子节点
        if(current.rightTree == node){
            while(current.parent != null){
                if(current == current.parent.leftChild)
                    return current.parent;  // ⑤ 若一个祖节点是其父节点的左子节点，则返回该祖节点的父节点
                else
                    current = current.parent;
            }
            return null;  // ⑥ 若没有一个祖节点是其父节点的左子节点，则返回空指针
        }  // end if

        return null;  // ⑦ 树结构错误，返回空指针
    }  // end getNext()

    /** 辅助代码-------------------------------- */

    /**
     * 连接节点
     */
    public static void connectTreeNodes(BinaryTreeNode parent,
                                   BinaryTreeNode leftChild, BinaryTreeNode rightChild){
        parent.leftChild = leftChild;
        parent.rightTree = rightChild;

        if(leftChild != null)
            leftChild.parent = parent;
        if(rightChild != null)
            rightChild.parent = parent;
    }  // end connectNode()

}  // end class
